[수학] 정보보호와 현대 수학 - 공개키 암호와 수학

1. (RSA) 큰 솟수 찾기 (쉬움)
큰수의 소인수 분해 (어려움)

2. (Diffie-Hellman 타입) 모듈러 멱승 (modular exponentiation) (쉬움)
이산대수 문제 풀기 (Discrete logarithm problem) (어려움)

3. NTRU -Lattice에서 shortest vector 찾기

4. 비가환군 이용 ...

5. 차세대 공개키 암호 시스템??

2.1 이산대수문제를 이용한 암호 시스템

이산대수 문제의 어려움을 이용한 Elgamal 암호시스템을 간단히 소개해 보자.

이산대수문제
를 개의 원소를 갖는 체(field)라 하고 를 의 생성원(generator)이라 하자. 라 하고 와 를 알 때 (여기서 는 1과 사이의 정수라 가정하자)를 수하는 문제를 이산대수 문제라 한다.

2.2 예

2.3 Elgamal 암호시스템

Elgamal 암호시스템 :
유한체 와 생성원는 알려졌다 하자.

1. 각 사용자 는 사이의 정수를 임의로(randomly) 선택 비밀로 간직한다.

2. 사용자 는 를 계산 이를 그의 enciphering key로 공개한다.

3. 비밀 메시지 를 에게 보내고자 하는 는 정수 를 임의(randomly)로 선택하여 와 를 계산한 후 에 속한 다음의 두 원소를 보낸다.

이 때 메시지 는 이미 의 원소로 전환되어 있음을 가정했고 의 계산은 의 공개키 를 보고 를 계산한 것이다.

4. 는 첫째 원소 를 사용 자신의 비밀키 로 를 계산한 후 둘째 원소에 에 나누어 를 구한다.
이 때 를 모르고 만으로 를 구하는 일은 어려운 일임을 알 수 있다.


제3절 현재 공개키 암호 시스템 동향

지금 현재의 컴퓨팅 파우어로는 유한체 위에서 이산 대수 문제의 어려움을 이용한 암호 시스템에서는 유한체 의 크기가 약 21200 정도가 되어야 암호시스템이 안전함을 알 수 있으며 사용자의

보관중인 자료가 없습니다